Systems for optically scanning patterns and then analyzing the data to "recognize" the patterns are well known in the art and are now a part of everyday life for most people. The most common form of optical pattern recognition is depicted in FIG. 1 as a simplified version of the common linear or one-dimensional bar code 10. One-dimensional bar codes appear on virtually all products and are scanned by fixed or hand-held scanners by checkout clerks and the like.
As depicted in FIGS. 1 and 2, a scanning beam 12 is scanned across the bar code 10 by the scanning device. A string of reflectance values are thereby produced which represent the transitions from bars to spaces along the scanning beam 12. Alternatively, an entire image or "snapshot" of the symbol 10 is taken by the reader. The data as reflected from the bar code 10 is then placed into a computer memory 14 on a pixel-by-pixel basis as pixel data 16, as depicted in FIG. 3 where each square in FIG. 3 represents a unique memory location. Since the data is one dimensional, it does not really matter whether the scanning takes place perpendicular to the bar code 10 as depicted in FIG. 1 or at an angle as depicted in FIG. 2. Similarly, it does not matter whether the pixel data 16 are located one-dimensionally or two-dimensionally within the computer memory 14 since it is an easy matter to analyze the data to determine the contents thereof
Optical Character Recognition (OCR) as it relates to the ability to "read" alphanumeric characters is another matter since the data are now related to a two-dimensional character. Thus, the problem is different if a character 18 being "scanned" is oriented in a known perpendicular direction as in FIG. 4 or skewed as in FIG. 5. While the character 18 can be scanned on a line-by-line basis by a raster scanning technique, it is easier and most common to simply view the character 18 two-dimensionally with, for example, a charge coupled device (CCD) camera which provides pixel data 16 within a computer memory 14 in the manner depicted in FIG. 6.
The contents of the computer memory 14 must then be analyzed on a correlated line-by-line basis as depicted in FIG. 7. The prior art techniques for analyzing the data from each line 20 of the memory 14 are complex and time-consuming, particularly if multiple fonts are to be "recognized" and orientations other than perpendicular are to be included. As can be appreciated, the prior art methodology of character recognition from the data 16 on a horizontal and vertical basis (i.e., line-by-line forward and backward and across each line pixel position-by-pixel position) cannot be accomplished in real-time. That is, the data must be scanned and they analyzed in a process that can literally take minutes for a standard page of characters.
Recently, there is a movement towards implementing area or two-dimensional bar codes to mark products. One-dimensional bar codes simply cannot contain enough data within a reasonable space. A so-called "SKU" or inventory identification number is about the limit of their ability.
By going to a two-dimensional bar code as depicted in FIG. 8, much more data can be represented in a much smaller space. FIG. 8 shows a so-called "Code-One" type of bar code 22. Code-One bar codes are of various types; but, each contains two components--an orientation pattern 24 and attached 2D data 26. A portion of the orientation pattern 24 from the bar code 22 of FIG. 8 is shown in FIG. 9. The orientation pattern 24 comprises a central portion 28 that defines the type of Code-One bar code present and is uniquely identifiable and locatable as to orientation; and, peripheral portions 30 that define the extents and sizing of the 2D data 26.
For our purposes, it is the central portion 28 that is of interest. The central portion 28 has a plurality of "vertical" edges 32 and "horizontal" edges 34 when the bar code 22 is in its proper orientation, and the edges are in a fixed relationship to one another. Thus, regardless of the orientation, if the vertical and horizontal edges can be found, the type of bar code 22 can be determined, its orientation can be determined, and the 2D data 26 can be interpreted.
FIG. 10 shows another two-dimensional symbol, namely a PDF 417 symbol 40. The orientation pattern consists of start and stop patterns 42 and 44. The start and stop patterns include very large or wide, bars relative to the rest of the symbol, 46 and 48, respectively. The bars 46 and 48 can be found within the stored image (e.g., by locating their elongated edges), and thus the position and type of the bar code 40 can be determined. Thereafter, three rows of bars and spaces 39 positioned between the start and stop patterns 42 and 44 can be decoded.
Prior art techniques still approach the problem in the same manner as working with alphanumeric data as described above. All the pixels of the scanned 2D image are stored in a computer memory and then the data are analyzed on a line-by-line basis trying to make sense of it. As can be appreciated, there is a big difference between recognizing an "H" surrounded by white space and recognizing one of many orientation patterns 24 within the bar code 22 as in FIG. 8, or the start and stop patterns 42 and 44 within the bar code 40 as shown in FIG. 10.
When it comes to scanning these two-dimensional bar codes at a point of sale, work station, or the like, there is not time for a recognition process which takes minutes to accomplish. The finding and unpacking of the data must take place in real-time or close to real-time. A typical consumer requirement is to have the data available in one second or less. Therefore, it is desirable to provide a method of analyzing optically scanned data associated with two-dimensional symbols or characters which can find and unpack the data in real-time or close to real-time.